// https://leetcode.cn/problems/add-binary/description/

// 算法思路总结：
// 1. 模拟二进制加法运算，从低位到高位逐位相加
// 2. 双指针分别指向两个字符串的末尾
// 3. 处理进位，当前位结果 = 各位和 % 2，进位 = 各位和 / 2
// 4. 注意处理两个字符串长度不等和最终进位的情况
// 5. 结果需要反转得到正确顺序
// 6. 时间复杂度：O(max(m,n))，空间复杂度：O(max(m,n))

#include <iostream>
using namespace std;

#include <string>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    string addBinary(string a, string b)
    {
        int m = a.size(), n = b.size();
        int cur1 = m - 1, cur2 = n - 1, carry = 0;
        string res;

        while(cur1 >= 0 || cur2 >= 0 || carry)
        {
            int tmp = 0;
            if (cur1 >= 0)  tmp += (a[cur1--] - '0');
            if (cur2 >= 0)  tmp += (b[cur2--] - '0');
            tmp += carry;
            res.push_back((tmp % 2) + '0');
            carry = tmp / 2;
        }
        reverse(res.begin(), res.end());

        return res;  
    }
};

int main()
{
    string s11 = "11", s12 = "1";
    string s21 = "1010", s22 = "1011";

    Solution sol;

    cout << sol.addBinary(s11, s12) << endl;
    cout << sol.addBinary(s21, s22) << endl;

    return 0;
}